package com.lry.basic.algorithm.dp;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/6/24
 */
//若干数和为k
public class SumK {
    static int n=4;
    static int [] num ={1,3,5,7};
    static int k=14;
    public static void main(String[] args) {
        System.out.println(sumK());
    }
//    dp[i+1][j]表示前i个数能否能否选择若干数和为k
    //每个数字只能选择一次
    public static boolean sumK(){
        boolean [][]dp = new boolean[n+1][k+1];
        for(int i=0;i<n;i++){
            dp[i][0]=true;
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<=k;j++){
                dp[i+1][j] = dp[i][j];
                if(j-num[i]>=0){
                    dp[i+1][j]|=dp[i][j-num[i]];
                }
            }
        }
        return dp[n][k];
    }
}
